# !/usr/usuari/des python
#  -*- coding: utf-8 -*-
"""
@Author        : itgnay
@Time          : 2022/12/22 22:16
@FileName      : 归并算法.py
@LastEditors   : None
@Editors       : PyCharm
"""
# 稳定
'''据说是效率很高的算法'''


def merge_sort(arr, p, q):
    if len(arr) == 0 or p >= q:
        return
    mid = int((p + q) / 2)
    merge_sort(arr, p, mid)
    merge_sort(arr, mid + 1, q)
    merge(arr, p - 1, mid, q)


def merge(arr, p, mid, q):
    length = q - p
    list1 = arr[p:mid] + [float('inf')]
    list2 = arr[mid:q] + [float('inf')]
    i = j = 0
    n = p
    while i + j < length:
        if list1[i] < list2[j]:
            arr[n] = list1[i]
            i += 1
        else:
            arr[n] = list2[j]
            j += 1
        n += 1


arr = [7, 5, 2, 4, 1, 6, 3, 0]
# 对 arr 数组中第 1 至 8 个元素做归并排序操作
merge_sort(arr, 1, 8)
print(arr)
